πŸ‘©β€πŸ’» 92345. μ‚¬λΌμ§€λŠ” 발판

@Seongukbaek Posted July 17, 2022 Β· Updated July 17, 2022 Β· 4 min read

문제

Programmers - μ‚¬λΌμ§€λŠ” 발판

πŸ“ Logic

private Result dfs(int aX, int aY, int bX, int bY, int moveA, int moveB) { boolean win = false; int minCount = 5 * 5; int maxCount = moveA + moveB; if (moveA == moveB && board[aX][aY] == 1) { // aκ°€ 움직일 μ°¨λ‘€ for (int[] d : dir) { int naX = aX + d[0]; int naY = aY + d[1]; if (!checkBoundary(naX, naY)) continue; board[aX][aY] = 0; Result r = dfs(naX, naY, bX, bY, moveA + 1, moveB); win |= !r.win; if (!r.win) minCount = Math.min(minCount, r.count); else maxCount = Math.max(maxCount, r.count); board[aX][aY] = 1; } } else if (moveA > moveB && board[bX][bY] == 1) { // bκ°€ 움직일 μ°¨λ‘€ for (int[] d : dir) { int nbX = bX + d[0]; int nbY = bY + d[1]; if (!checkBoundary(nbX, nbY)) continue; board[bX][bY] = 0; // dfs의 κ²°κ³ΌλŠ” 본인이 μ•„λ‹Œ λ‹€λ₯Έ μ‚¬λžŒμ˜ κ²°κ³Όμ΄λ―€λ‘œ, μŠΉνŒ¨κ°€ λ°˜λŒ€μ΄λ‹€. // λ˜ν•œ r.win = true인 κ²½μš°κ°€ ν•˜λ‚˜λΌλ„ μžˆμ„ 경우 win은 trueκ°€ λ˜μ–΄μ•Ό ν•˜λ―€λ‘œ or연산을 μˆ˜ν–‰ν•œλ‹€. Result r = dfs(aX, aY, nbX, nbY, moveA, moveB + 1); win |= !r.win; // 본인이 μ΄κΈ°λŠ” 경우라면 μ΅œλŒ€ν•œ 빨리 이길 λ•Œμ˜ μ΄λ™νšŸμˆ˜λ₯Ό κ°±μ‹ ν•œλ‹€. if (!r.win) minCount = Math.min(minCount, r.count); // 본인이 μ§€λŠ” 경우라면 μ΅œλŒ€ν•œ 였래 버틸 λ•Œμ˜ μ΄λ™νšŸμˆ˜λ₯Ό κ°±μ‹ ν•œλ‹€. else maxCount = Math.max(maxCount, r.count); board[bX][bY] = 1; } } return new Result(win, win ? minCount : maxCount); }
  • Aκ°€ 움직일 차둀와, Bκ°€ 움직일 μ°¨λ‘€λ₯Ό λ‚˜λˆ„μ–΄ μƒκ°ν•œλ‹€.
  • DFSλ°©μ‹μœΌλ‘œ μ›€μ§μ΄λ©΄μ„œ, μ΄κΈ°λŠ” κ²½μš°μ™€ μ§€λŠ” 경우의 μ΄λ™νšŸμˆ˜λ₯Ό κ°±μ‹ ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Result { boolean win; int count; public Result(boolean win, int count) { this.win = win; this.count = count; } } class Solution { static int[][] dir = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }}; static int[][] board; static int N; static int M; public int solution(int[][] board, int[] aloc, int[] bloc) { this.board = board; this.N = board.length; this.M = board[0].length; return dfs(aloc[0], aloc[1], bloc[0], bloc[1], 0, 0).count; } private Result dfs(int aX, int aY, int bX, int bY, int moveA, int moveB) { boolean win = false; int minCount = 5 * 5; int maxCount = moveA + moveB; if (moveA == moveB && board[aX][aY] == 1) { // aκ°€ 움직일 μ°¨λ‘€ for (int[] d : dir) { int naX = aX + d[0]; int naY = aY + d[1]; if (!checkBoundary(naX, naY)) continue; board[aX][aY] = 0; Result r = dfs(naX, naY, bX, bY, moveA + 1, moveB); win |= !r.win; if (!r.win) minCount = Math.min(minCount, r.count); else maxCount = Math.max(maxCount, r.count); board[aX][aY] = 1; } } else if (moveA > moveB && board[bX][bY] == 1) { // bκ°€ 움직일 μ°¨λ‘€ for (int[] d : dir) { int nbX = bX + d[0]; int nbY = bY + d[1]; if (!checkBoundary(nbX, nbY)) continue; board[bX][bY] = 0; // dfs의 κ²°κ³ΌλŠ” 본인이 μ•„λ‹Œ λ‹€λ₯Έ μ‚¬λžŒμ˜ κ²°κ³Όμ΄λ―€λ‘œ, μŠΉνŒ¨κ°€ λ°˜λŒ€μ΄λ‹€. // λ˜ν•œ r.win = true인 κ²½μš°κ°€ ν•˜λ‚˜λΌλ„ μžˆμ„ 경우 win은 trueκ°€ λ˜μ–΄μ•Ό ν•˜λ―€λ‘œ or연산을 μˆ˜ν–‰ν•œλ‹€. Result r = dfs(aX, aY, nbX, nbY, moveA, moveB + 1); win |= !r.win; // 본인이 μ΄κΈ°λŠ” 경우라면 μ΅œλŒ€ν•œ 빨리 이길 λ•Œμ˜ μ΄λ™νšŸμˆ˜λ₯Ό κ°±μ‹ ν•œλ‹€. if (!r.win) minCount = Math.min(minCount, r.count); // 본인이 μ§€λŠ” 경우라면 μ΅œλŒ€ν•œ 였래 버틸 λ•Œμ˜ μ΄λ™νšŸμˆ˜λ₯Ό κ°±μ‹ ν•œλ‹€. else maxCount = Math.max(maxCount, r.count); board[bX][bY] = 1; } } return new Result(win, win ? minCount : maxCount); } private boolean checkBoundary(int x, int y) { return (x >= 0 && x < N && y >= 0 && y < M && board[x][y] != 0) ; } }

✏️ Review

  • 이길 수 μžˆλŠ” ν”Œλ ˆμ΄μ–΄λŠ” μ΅œλŒ€ν•œ 빨리 μŠΉλ¦¬ν•˜κ³ , 질 μˆ˜λ°–μ— μ—†λŠ” ν”Œλ ˆμ΄μ–΄λŠ” μ΅œλŒ€ν•œ 였래 λ²„ν‹΄λ‹€λΌλŠ” 쑰건에 μžˆμ–΄ 쑰금 λ…νŠΉν•œ λ¬Έμ œκ°€ μ•„λ‹ˆμ—ˆλ‚˜μ‹Άλ‹€.
  • μ€‘λ³΅λ˜λŠ” λ‘œμ§μ„ λ–Όλ‚΄μ–΄μ•Ό ν•  것 κ°™λ‹€.
  • μ—­μ‹œ λ§ˆμ§€λ§‰ λ¬Έμ œλŠ” μ–΄λ ΅λ‹€ ...
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€